#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
//https://www.luogu.com.cn/problem/P4139
using namespace std;
using LL = long long;

const int N = 1e7 + 10;
int T, m;
LL phi[N], p[N];
int cnt = 0;
bool st[N];
void get_phi()
{
	int n = 1e7;
	phi[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (!st[i])
		{
			p[++cnt] = i;
			phi[i] = i - 1;
		}

		for (int j = 1; 1ll * p[j] * i <= n; ++j)
		{
			LL x = 1ll * p[j] * i;
			st[x] = true;
			if (i % p[j])
			{
				phi[x] = (p[j] - 1) * phi[i];
			}
			else
			{
				phi[x] = (p[j]) * phi[i];
				break;
			}
		}

	}

}

LL qpow(LL a, LL b, LL m)
{
	LL ret = 1;
	while (b)
	{
		if (b & 1)ret = ret * a % m;
		b >>= 1;
		a = a * a % m;
	}
	return ret;
}

LL dfs(LL m)
{
	if (m <= 1)return 0;
	return qpow(2, dfs(phi[m]) + phi[m], m);
}


int main()
{
	get_phi();
	cin >> T;
	while (T--)
	{
		cin >> m;

		cout << dfs(m)<<endl;

	}

	return 0;
}